package algorithm

import "fmt"

type Heap struct {
	data []int
	length int
}

func (h *Heap) Insert(v int)  {
	h.data = append(h.data, v)
	h.adjustUp()
	h.length++
}

func (h *Heap) adjustUp()  {
	l:=len(h.data)
	if l<=1{
		return
	}
	if l==2{
		if h.data[0]<h.data[1]{
			h.swap(0,1)
		}
		return
	}
	i:=l-1
	for{
		p:=i/2
		if h.data[i]>h.data[p]{
			h.swap(i,p)
		}

		i=p
		if i<=0{
			return
		}
	}
}

func (h *Heap) siftDown() {
	l:=h.length
	if l<=1{
		return
	}
	if l==2{
		if h.data[0]>h.data[1]{
			h.swap(0,1)
		}
		h.length=0
		return
	}
	h.swap(0,l-1)
	h.length--
	i:=0
	for{
		left:=2*i+1
		if left>=h.length{
			break
		}
		right:=2*i+2
		max:=left
		if right<h.length{
			if h.data[right]>h.data[left]{
				max=right
			}
		}
		if h.data[max]>h.data[i]{
			h.swap(i,max)
		}else {
			break
		}
		i=max
	}
}

func (h *Heap) GetTop() int {
	if len(h.data)==0{
		panic("empty heap")
	}
	return h.data[0]
}

func (h *Heap) swap(i,j int)  {
	t:=h.data[i]
	h.data[i]=h.data[j]
	h.data[j]=t
}

func (h *Heap) Show()  {
	for _,v:=range h.data{
		fmt.Print(v," ")
	}
}
//堆排序
func (h *Heap) HeapSort()  {
	for i:=0;i<len(h.data)-1;i++{
		h.siftDown()
	}
}
